package 我的Java学习_算法基础.day_05;

public class HeightArray {
    public static int[] getHeight(String src,Suff[] sa){
        int strLength = src.length();
        int[] rk = new int[strLength];
        //将rank表示为不重复的排名即0~n-1
        for(int i =0;i<strLength;i++){
            rk[sa[i].index] = i;
        }
        int[] height = new int[strLength];
        //若果已经知道后缀数组中i和i+1的lcp为h，那么i代表的字符串与i+1代表的字符串去掉首字母的lcp为h-1
        //根据这个，如果知道i与后缀数组中在它后一个的lcp为k，那么它去掉首字母后的字符串与其在后缀数组中的后一个的lcp大于等于k-1
        //例如对于字符串abcefabc,我们知道abcefabc与abc的lcp为3
        //那么bcefab与bc的lcp大于等于3-1
        //利用这一点就可以O(N)求出高度数组
        //lcp: longest common prefix
        int k = 0;
        for(int i =0;i<strLength;i++){
            int rk_i = rk[i];//i后缀的排名
            if(rk_i==0){
                height[0] = 0;
                continue;
            }
            int rk_i_1 = rk_i-1;
            int j = sa[rk_i_1].index;//j是i串字典序靠前的串的下标
            if(k>0) k--;
            for(;j+k<strLength&&i+k<strLength;k++){
                if(src.charAt(j+k)!=src.charAt(i+k))
                    break;
            }
            height[rk_i] = k;
        }
        return height;
    }
}
